package com.markus.code.排序.base;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/4 20:54
 * todo:
 */
public class HeapSort {
    public static void heapSort(int []arr){
        if (arr == null || arr.length == 0){
            return ;
        }
        //建大顶堆
        for (int i=0;i<arr.length;i++){
            buildHeap(arr,i);
        }
//        for (int i : arr) {
//            System.out.print(i+" ");
//        }
        int size = arr.length-1;
        while(size > 0){
            swap(arr,0,size);
            heapify(arr,0,size-1);
            size--;
        }
    }
    private static void buildHeap(int []arr,int index){
        int parentIndex = (index-1)/2;//得到父节点的索引
        while(arr[index] > arr[parentIndex]){
            swap(arr,index,parentIndex);
            index = parentIndex;
            parentIndex = (index-1)/2;
        }
    }
    //将头节点向下压
    private static void heapify(int []arr,int index,int len){
        int leftIndex = 2*index+1;
        while (leftIndex < len){
            int maxValueIndex = leftIndex+1<len &&
                    arr[leftIndex]<arr[leftIndex+1]?leftIndex+1:leftIndex;
            if (arr[maxValueIndex] < arr[index]){
                break;
            }
            swap(arr,maxValueIndex,index);
            index = leftIndex;
            leftIndex = 2*index+1;
        }
    }

    private static void swap(int []arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int []arr = {3,6,4,7,1,8,1,5,5,9,6};
        heapSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
